import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param p int整型
     * @param q int整型
     * @return int整型
     */

    //判断一颗二叉树是否包含某个数
    private boolean containsNode(TreeNode root,int target){

        if(root==null){
            return false;
        }
        if(root.val==target){
            return true;
        }
        if(containsNode(root.left,target)){
            return true;
        }
        return containsNode(root.right,target);
    }
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
//分情况：p,q其中有一个是当前的root,那么直接返回root.val
//p,q都不是当前的root,两个都在左子树，那么到左子树root.left找
//p,q都不是当前的root,两个都在右子树，那么到左子树root.right找
//p,q一左一右，最近公共祖先是root
        if(p==root.val||q==root.val){
            return root.val;
        }

        boolean inPLeft=containsNode(root.left,p);
        boolean inQLeft=containsNode(root.left,q);

        if(inPLeft&&inQLeft){
            return lowestCommonAncestor(root.left,p,q);
        }
        if(!inPLeft&&!inQLeft){
            return lowestCommonAncestor(root.right,p,q);
        }

        return root.val;
    }
}